package _17_剑指Offer;

import java.util.Arrays;
import java.util.PriorityQueue;

public class _40_剑指Offer最小的k个数 {

    public static void main(String[] args) {

        _40_剑指Offer最小的k个数 v = new _40_剑指Offer最小的k个数();
        int[] ins = {0, 0, 1, 2, 0};
        System.out.println(Arrays.toString(v.getLeastNumbers(ins, 3)));

    }

    // 使用快速排序
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        return quickSort(arr, 0, arr.length - 1, k - 1);
    }

    private int[] quickSort(int[] arr, int begin, int end, int k) {
        int h = pivotIndex(arr, begin, end);
        if (h == k) {
            return Arrays.copyOf(arr, k + 1);
        }
        return h > k? quickSort(arr, begin, h - 1, k): quickSort(arr, h + 1, end, k);
    }

    private int pivotIndex(int[] arr, int begin, int end) {
        int v = arr[begin];
        while (begin < end) {
            while (begin < end) {
                if (arr[end] > v) end--;
                else {
                    arr[begin++] = arr[end];
                    break;
                }
            }
            while (begin < end) {
                if (arr[begin] < v) begin++;
                else {
                    arr[end--] = arr[begin];
                    break;
                }
            }
        }
        arr[begin] = v;
        return begin;
    }

    // 使用大顶堆
    public int[] getLeastNumbers2(int[] arr, int k) {
        if (arr.length < k) return arr;
        if (k == 0) return new int[0];
        PriorityQueue<Integer> queue = new PriorityQueue<>((a1, a2) -> a2 - a1);

        for (int ele : arr) {
            if (queue.size() < k) {
                // 直接添加
                queue.offer(ele);
                continue;
            }

            // 大于忽略
            if (queue.peek() < ele) continue;
            queue.poll();
            queue.offer(ele);
        }

        int[] results = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            results[i] = queue.poll();
        }
        return results;
    }

    // 排序
    public int[] getLeastNumbers1(int[] arr, int k) {
        if (arr.length < k) return arr;
        Arrays.sort(arr);

        int[] results = new int[k];
        System.arraycopy(arr, 0, results, 0, k);
        return results;
    }
}
